package Data_Structure.List.MyList;

/**
 * @className: MyLinkedList
 * @author: 芃
 * @description: 单向链表->物理地址不连续 由节点组成 简易版本
 * @date: 2023/8/16 12:28
 */
public class MyLinkedList {
    private Node head;

    //头插法
    public void addFirst(int val){
        Node node = new Node(val);
        node.next = head;
        head = node;
    }

    //尾插法
    public void addEnd(int val){
        Node node = new Node(val);
        if (head == null){
            //链表为空
            head = node;
        }else {
            //链表不为空
            Node cur = head;
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //找到index-1位置的节点的地址
    private Node findIndex(int index){
        Node cur = this.head;
        while (index-1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入
    public void addIndex(int index,int val){
        if (index < 0 || index > size()){
            System.out.println("插入位置不合法，插入失败~");
            return;
        }
        //头插
        if (index == 0){
            addFirst(val);
            return;
        }
        //尾插
        if (index == size()){
            addEnd(val);
            return;
        }
        //获取插入下标的前一个节点
        Node pre = findIndex(index);
        Node next = pre.next;
        Node tmp = new Node(val);
        pre.next = tmp;
        tmp.next = next;
    }

    //查找是否包含关键字Key-是否在单链表中
    public boolean contains(int key){
        Node cur = this.head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //找到要删除的关键字的前驱
    public Node searchPrev(int key){
        Node cur = this.head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void delete(int key){
        if (this.head == null){
            System.out.println("链表为空~");
        }else {//链表非空
            //如果要删除的是头节点
            if (this.head.val == key){
                this.head = this.head.next;
            }else {//非头节点
                Node prev = searchPrev(key);
                if (prev == null){
                    System.out.println("没有找到值为" + key + "的节点，删除失败~");
                }else {
                    prev.next = prev.next.next;
                }
            }
        }
    }

    //删除所有值为key的节点
    public Node deleteAll(int key){
        if (this.head == null){
            return null;
        }
        Node prev = this.head;
        Node cur = this.head.next;
        while (cur != null){
            if (cur.val == key){
                prev.next = cur.next;
            }else {
                prev = cur;
            }
            cur = cur.next;
        }
        //检查头节点
        if (head.val == key){
            head = head.next;
        }
        return head;
    }

    //得到单链表的长度
    public int size(){
        Node cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //单链表打印
    public void print(){
        Node cur = head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //清空单链表
    public void clear(){
        this.head = null;
    }

}
